/*
 * @Description: 
 * @Autor: yanwang
 * @Date: 2021-11-09 16:23:57
 * @LastEditors: yanwang
 * @LastEditTime: 2021-11-09 17:49:14
 */
/*
 * @lc app=leetcode.cn id=1268 lang=typescript
 *
 * [1268] 搜索推荐系统
 */

// @lc code=start
class TrieNode {
  flag: boolean = false
  next: any[] = []
  pro: string[] = []; // 存放经过此节点的 word
}
function insert(word, root) {
  let p = root;
  for (let x of word) {
    const ind = x.charCodeAt(0) - 'a'.charCodeAt(0);

    if(!p.next[ind]) p.next[ind] = new TrieNode();
    p = p.next[ind];

    p.pro.push(word); // 存入此单词
    p.pro.sort();
    if(p.pro.length > 3) p.pro.pop(); // 超过3个则删除最大的
  }
}

function search(word, root) {
  let p = root, ret = [];
  for (let x of word) {
    const ind = x.charCodeAt(0) - 'a'.charCodeAt(0);
    
    if(p.next[ind]) {
      p = p.next[ind];
      ret.push(p.pro);
    } else {
      ret.push([]);
      p = new TrieNode(); // 将p放置到一个空节点
    }
  }
  return ret;
}

function suggestedProducts(products: string[], searchWord: string): string[][] {
  const root = new TrieNode();

  for (let i = 0; i < products.length; i++) {
    insert(products[i], root);
  }
  
  return search(searchWord, root);
};
// @lc code=end

